Combination sum II

Time: O(KxC(N,K)); Space: O(K); medium

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Notes:

  • All numbers (including target) will be positive integers.

  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8

Output:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5

Output:

[
  [1,2,2],
  [5]
]

[6]:

class Solution1(object):
    """
    Time: O(K*C(N,K))
    Space: O(K)
    """
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        self.combinationSumRecu(sorted(candidates), result, 0, [], target)
        return result

    def combinationSumRecu(self, candidates, result, start, intermediate, target):
        if target == 0:
            result.append(list(intermediate))
        prev = 0

        while start < len(candidates) and candidates[start] <= target:
            if prev != candidates[start]:
                intermediate.append(candidates[start])
                self.combinationSumRecu(candidates, result, start + 1, intermediate, target - candidates[start])
                intermediate.pop()
                prev = candidates[start]
            start += 1

[7]:

s = Solution1()

candidates = [10,1,2,7,6,1,5]
target = 8
assert s.combinationSum2(candidates, target) == [
  [1, 1, 6],
  [1, 2, 5],
  [1, 7],
  [2, 6],
]

candidates = [2,5,2,1,2]
target = 5
assert s.combinationSum2(candidates, target) == [[1,2,2], [5]]